package smlab.astar
{
    import flash.geom.*;

    public class AStar extends Object
    {
        private var _fatherList:Array;
        private const NOTE_ID:int = 0;
        private var _noteMap:Array;
        private var _maxTry:int;
        private const NOTE_CLOSED:int = 2;
        private var _nodeList:Array;
        private var _openId:int;
        private var _openCount:int;
        private const COST_DIAGONAL:int = 14;
        private var _pathScoreList:Array;
        private var _openList:Array;
        private const COST_STRAIGHT:int = 10;
        private const NOTE_OPEN:int = 1;
        private var _movementCostList:Array;
        public static const aroundsData:Array = [new Point(1, 0), new Point(0, 1), new Point(-1, 0), new Point(0, -1), new Point(1, 1), new Point(-1, 1), new Point(-1, -1), new Point(1, -1)];
        private static var _instance:AStar;
		private var _mapModel:MapModel;
        public function AStar()
        {
            return;
        }

        private function isBlock(p:Point) : Boolean
        {
            if (p.x >= 0)
            {
            }
            if (p.x < _mapModel.gridX)
            {
            }
            if (p.y >= 0)
            {
            }
            if (p.y >= _mapModel.gridY)
            {
                return false;
            }
            return _mapModel.data[p.x][p.y];
        }

        private function _find(p_start:Point, p_end:Point) : Array
        {
            var _loc_5:int = 0;
            var _loc_6:Point = null;
            var _loc_7:int = 0;
            var _loc_8:int = 0;
            var _loc_9:int = 0;
            var _loc_10:Array = null;
            var _loc_11:Point = null;
            if (_mapModel == null)
            {
                return null;
            }
            p_start = transPoint(p_start);
            var _loc_3:* = transPoint(p_end.clone());
            if (!isBlock(_loc_3))
            {
                return null;
            }
            initLists();
            _openCount = 0;
            _openId = -1;
            openNote(p_start, 0, 0, 0);
            var _loc_4:int = 0;
            while (_openCount > 0)
            {
                
                if (++_loc_4 > _maxTry)
                {
                    destroyLists();
                    return null;
                }
                _loc_5 = _openList[0];
                closeNote(_loc_5);
                _loc_6 = _nodeList[_loc_5];
                if (_loc_3.equals(_loc_6))
                {
                    return getPath(p_start, _loc_5);
                }
                _loc_10 = getArounds(_loc_6);
                for each (_loc_11 in _loc_10)
                {
                    
                    if (_loc_11.x != _loc_6.x)
                    {
                    }
                    _loc_8 = _movementCostList[_loc_5] + (_loc_11.y == _loc_6.y ? (COST_STRAIGHT) : (COST_DIAGONAL));
                    _loc_9 = _loc_8 + (Math.abs(_loc_3.x - _loc_11.x) + Math.abs(_loc_3.y - _loc_11.y)) * COST_STRAIGHT;
                    if (isOpen(_loc_11))
                    {
                        _loc_7 = _noteMap[_loc_11.y][_loc_11.x][NOTE_ID];
                        if (_loc_8 < _movementCostList[_loc_7])
                        {
                            _movementCostList[_loc_7] = _loc_8;
                            _pathScoreList[_loc_7] = _loc_9;
                            _fatherList[_loc_7] = _loc_5;
                            aheadNote((_openList.indexOf(_loc_7) + 1));
                        }
                        continue;
                    }
                    openNote(_loc_11, _loc_9, _loc_8, _loc_5);
                }
            }
            destroyLists();
            return null;
        }

        private function closeNote(p_id:int) : void
        {
            var _loc_4:* = _openCount - 1;
            _openCount = _loc_4;
            var _loc_2:* = _nodeList[p_id];
            _noteMap[_loc_2.y][_loc_2.x][NOTE_OPEN] = false;
            _noteMap[_loc_2.y][_loc_2.x][NOTE_CLOSED] = true;
            if (_openCount <= 0)
            {
                _openCount = 0;
                _openList = [];
                return;
            }
            _openList[0] = _openList.pop();
            backNote();
            return;
        }

        private function isOpen(p:Point) : Boolean
        {
            if (_noteMap[p.y] == null)
            {
                return false;
            }
            if (_noteMap[p.y][p.x] == null)
            {
                return false;
            }
            return _noteMap[p.y][p.x][NOTE_OPEN];
        }

        private function getArounds(p:Point) : Array
        {
            var _loc_3:Point = null;
            var _loc_4:Boolean = false;
            var _loc_2:Array = [];
            var _loc_5:int = 0;
            _loc_3 = p.add(aroundsData[_loc_5]);
            _loc_5 = _loc_5 + 1;
            var _loc_6:* = isBlock(_loc_3);
            if (_loc_6)
            {
            }
            if (!isClosed(_loc_3))
            {
                _loc_2.push(_loc_3);
            }
            _loc_3 = p.add(aroundsData[_loc_5]);
            _loc_5 = _loc_5 + 1;
            var _loc_7:* = isBlock(_loc_3);
            if (_loc_7)
            {
            }
            if (!isClosed(_loc_3))
            {
                _loc_2.push(_loc_3);
            }
            _loc_3 = p.add(aroundsData[_loc_5]);
            _loc_5 = _loc_5 + 1;
            var _loc_8:* = isBlock(_loc_3);
            if (_loc_8)
            {
            }
            if (!isClosed(_loc_3))
            {
                _loc_2.push(_loc_3);
            }
            _loc_3 = p.add(aroundsData[_loc_5]);
            _loc_5 = _loc_5 + 1;
            var _loc_9:* = isBlock(_loc_3);
            if (_loc_9)
            {
            }
            if (!isClosed(_loc_3))
            {
                _loc_2.push(_loc_3);
            }
            _loc_3 = p.add(aroundsData[_loc_5]);
            _loc_5 = _loc_5 + 1;
            _loc_4 = isBlock(_loc_3);
            if (_loc_4)
            {
            }
            if (_loc_6)
            {
            }
            if (_loc_7)
            {
            }
            if (!isClosed(_loc_3))
            {
                _loc_2.push(_loc_3);
            }
            _loc_3 = p.add(aroundsData[_loc_5]);
            _loc_5 = _loc_5 + 1;
            _loc_4 = isBlock(_loc_3);
            if (_loc_4)
            {
            }
            if (_loc_8)
            {
            }
            if (_loc_7)
            {
            }
            if (!isClosed(_loc_3))
            {
                _loc_2.push(_loc_3);
            }
            _loc_3 = p.add(aroundsData[_loc_5]);
            _loc_5 = _loc_5 + 1;
            _loc_4 = isBlock(_loc_3);
            if (_loc_4)
            {
            }
            if (_loc_8)
            {
            }
            if (_loc_9)
            {
            }
            if (!isClosed(_loc_3))
            {
                _loc_2.push(_loc_3);
            }
            _loc_3 = p.add(aroundsData[_loc_5]);
            _loc_5 = _loc_5 + 1;
            _loc_4 = isBlock(_loc_3);
            if (_loc_4)
            {
            }
            if (_loc_6)
            {
            }
            if (_loc_9)
            {
            }
            if (!isClosed(_loc_3))
            {
                _loc_2.push(_loc_3);
            }
            return _loc_2;
        }

        private function aheadNote(p_index:int) : void
        {
            var _loc_2:int = 0;
            var _loc_3:int = 0;
            while (p_index > 1)
            {
                
                _loc_2 = int(p_index / 2);
                if (getScore(p_index) < getScore(_loc_2))
                {
                    _loc_3 = _openList[(p_index - 1)];
                    _openList[(p_index - 1)] = _openList[(_loc_2 - 1)];
                    _openList[(_loc_2 - 1)] = _loc_3;
                    p_index = _loc_2;
                    continue;
                }
                break;
            }
            return;
        }

        private function backNote() : void
        {
            var _loc_2:int = 0;
            var _loc_3:int = 0;
            var _loc_1:int = 1;
            while (true)
            {
                
                _loc_2 = _loc_1;
                if (2 * _loc_2 <= _openCount)
                {
                    if (getScore(_loc_1) > getScore(2 * _loc_2))
                    {
                        _loc_1 = 2 * _loc_2;
                    }
                    if (2 * _loc_2 + 1 <= _openCount)
                    {
                        if (getScore(_loc_1) > getScore(2 * _loc_2 + 1))
                        {
                            _loc_1 = 2 * _loc_2 + 1;
                        }
                    }
                }
                if (_loc_2 == _loc_1)
                {
                    break;
                    continue;
                }
                _loc_3 = _openList[(_loc_2 - 1)];
                _openList[(_loc_2 - 1)] = _openList[(_loc_1 - 1)];
                _openList[(_loc_1 - 1)] = _loc_3;
            }
            return;
        }

        private function openNote(p:Point, p_score:int, p_cost:int, p_fatherId:int) : void
        {
            var _loc_6:* = _openCount + 1;
            _openCount = _loc_6;
            var _loc_62:* = _openId + 1;
            _openId = _loc_62;
            if (_noteMap[p.y] == null)
            {
                _noteMap[p.y] = [];
            }
            _noteMap[p.y][p.x] = [];
            _noteMap[p.y][p.x][NOTE_OPEN] = true;
            _noteMap[p.y][p.x][NOTE_ID] = _openId;
            _nodeList.push(p);
            _pathScoreList.push(p_score);
            _movementCostList.push(p_cost);
            _fatherList.push(p_fatherId);
            _openList.push(_openId);
            aheadNote(_openCount);
            return;
        }

        private function eachArray(element:Point, index:int, arr:Array) : void
        {
            element.x = element.x * _mapModel.gridSize;
            element.y = element.y * _mapModel.gridSize;
            return;
        }

        private function transPoint(p:Point) : Point
        {
            p.x = int(p.x / _mapModel.gridSize);
            p.y = int(p.y / _mapModel.gridSize);
            return p;
        }

        private function getPath(p_start:Point, p_id:int) : Array
        {
            var _loc_3:Array = [];
            var _loc_4:* = _nodeList[p_id];
            while (!p_start.equals(_loc_4))
            {
                
                _loc_3.push(_loc_4);
                p_id = _fatherList[p_id];
                _loc_4 = _nodeList[p_id];
            }
            _loc_3.push(p_start);
            destroyLists();
            _loc_3.reverse();
            optimize(_loc_3);
            _loc_3.forEach(eachArray);
            return _loc_3;
        }

        private function getScore(p_index:int) : int
        {
            return _pathScoreList[_openList[(p_index - 1)]];
        }

        private function initLists() : void
        {
            _openList = [];
            _nodeList = [];
            _pathScoreList = [];
            _movementCostList = [];
            _fatherList = [];
            _noteMap = [];
            return;
        }

        private function destroyLists() : void
        {
            _openList = null;
            _nodeList = null;
            _pathScoreList = null;
            _movementCostList = null;
            _fatherList = null;
            _noteMap = null;
            return;
        }

        private function isClosed(p:Point) : Boolean
        {
            if (_noteMap[p.y] == null)
            {
                return false;
            }
            if (_noteMap[p.y][p.x] == null)
            {
                return false;
            }
            return _noteMap[p.y][p.x][NOTE_CLOSED];
        }

        private function optimize(arr:Array, index:int = 0) : void
        {
            var _loc_5:Point = null;
            var _loc_6:int = 0;
            var _loc_7:Number = NaN;
            var _loc_10:int = 0;
            var _loc_11:int = 0;
            var _loc_12:Point = null;
            if (arr == null)
            {
                return;
            }
            var _loc_3:* = arr.length - 1;
            if (_loc_3 < 2)
            {
                return;
            }
            var _loc_4:* = arr[index];
            var _loc_8:Array = [];
            var _loc_9:* = _loc_3;
            while (_loc_9 > index)
            {
                
                _loc_5 = arr[_loc_9];
                _loc_6 = Point.distance(_loc_4, _loc_5);
                _loc_7 = Math.atan2(_loc_5.y - _loc_4.y, _loc_5.x - _loc_4.x);
                _loc_10 = 1;
                while (_loc_10 < _loc_6)
                {
                    
                    _loc_12 = _loc_4.add(Point.polar(_loc_10, _loc_7));
                    _loc_12.x = int(_loc_12.x);
                    _loc_12.y = int(_loc_12.y);
                    if (_mapModel.data[_loc_12.x][_loc_12.y])
                    {
                        _loc_8.push(_loc_12);
                    }
                    else
                    {
                        _loc_8 = [];
                        break;
                    }
                    _loc_10 = _loc_10 + 1;
                }
                _loc_11 = _loc_8.length;
                if (_loc_11 > 0)
                {
                    arr.splice((index + 1), _loc_9 - index - 1);
                    index = index + (_loc_11 - 1);
                    break;
                }
                _loc_9 = _loc_9 - 1;
            }
            if (index < _loc_3)
            {
                optimize(arr, ++index);
            }
            return;
        }

        public static function find(p_start:Point, p_end:Point) : Array
        {
            return getInstance()._find(p_start, p_end);
        }

        private static function getInstance() : AStar
        {
            if (_instance == null)
            {
                _instance = new AStar;
            }
            return _instance;
        }

        public static function get maxTry() : int
        {
            return getInstance()._maxTry;
        }

        public static function init(mapModel:MapModel, maxTry:int = 1000) : void
        {
            getInstance()._mapModel = mapModel;
            getInstance()._maxTry = maxTry;
            return;
        }

    }
}
